//给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
//
//
//
// 示例 1：
//
//
//输入：nums = [1,1,2]
//输出：
//[[1,1,2],
// [1,2,1],
// [2,1,1]]
//
//
// 示例 2：
//
//
//输入：nums = [1,2,3]
//输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
//
//
//
//
// 提示：
//
//
// 1 <= nums.length <= 8
// -10 <= nums[i] <= 10
//
// Related Topics 数组 回溯 👍 1092 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.*;

/**
 * [P47]_全排列 II
 * @author cjl
 * @date 2022-06-11 20:23:07
 */
public class P47_PermutationsIi{
      public static void main(String[] args) {
            //测试代码
           Solution solution = new P47_PermutationsIi().new Solution();
           solution.permuteUnique(new int[]{1,1,2});
      }
      //力扣代码
      //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
          /**
           * 回溯法：
           * 如何避免重复：
           * 1.数据排序
           * 2.同一位置，同一数据只被放置一次；即 i>0 且 nums[i] == nums[i-1] 且 第i-1个元素未填入时，不处理
           * @param nums
           * @return
           */
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> resList = new ArrayList<>();
        Arrays.sort(nums);
        List<Integer> curList = new ArrayList<>();//当前排列
        Set<Integer> hasUsedSet = new HashSet<>();//当前已使用下表
        permuteUqi(curList, nums, hasUsedSet, resList);
        return resList;
    }

    public void permuteUqi(List<Integer> currList, int[] nums, Set<Integer> hasUsedSet, List<List<Integer>> resList){
        if(nums.length == hasUsedSet.size()){
            resList.add(new ArrayList<>(currList));
        }
        for(int i = 0; i < nums.length; i++){
            if(hasUsedSet.contains(i) || (i > 0 && nums[i-1] == nums[i] && !hasUsedSet.contains(i-1))){
                continue;
            }
            //当前节点没有放入过
                //策略一：放入当前i；
                currList.add(nums[i]);
                hasUsedSet.add(i);
                permuteUqi(currList, nums, hasUsedSet,resList);
                //list 的remove 是移除第index位置的元素
                currList.remove(currList.size()-1);
                //set的 remove 是移除 某个key值；
                hasUsedSet.remove(i);
                //策略二：不放入当前i,即不处理
//                permuteUqi(currList, nums, hasUsedSet,resList);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

  }